1. Field of the Invention
The present invention relates generally to multiprocessors and more particularly to programs for allocating tasks among a plurality of processors connected together in a tightly-coupled multiprocessor configuration. It relates specifically to situations where the unit of work, or task, may be executed on only one processor at a time.
2. Background
Tightly coupled multiprocessing systems comprise two or more connected processors which share central storage, are capable of executing simultaneous instruction streams and which run under the control of a single operating system. An example of such a multiprocessor system is the IBM (IBM is a Registered Trademark) 3081K running under the control of the IBM Virtual Machine System Product High Performance Option (hereinafter "VM/SP HPO").
In such systems, typically there will be units of work, or tasks, (some or all of which can be executed by only one processor at a time) which enter the system or are generated by the system and which must at some time be dispatched by an available processor. Such systems typically use some data structure, such as a control block, to represent these tasks. This allows the system to maintain status for the task, and to place it on queues to await dispatch or to defer the execution of the task. Tasks represented in this manner will be called dispatchable tasks in this application.
Certain conditions may exist in a multiprocessor system such that a dispatchable task may not be run while these conditions persist. For example, a task may require that a supervisory function be performed on its behalf before it can run or continue to run. Until that function completes, the task is "not ready". Completion of the function "readies" the task, and the "readying" processor typically indicates this in the data structure representing the task.
In such systems, a processor is considered "active" when it is performing a task or when it is in the process of selecting a task to perform. A processor is considered "idle" when it has verified that there is no task available for it to perform.
Any single processor is Idle upon detecting that:
1. there are no readied dispatchable tasks available to the system or PA0 2. all readied dispatchable tasks are being processed by other processors or PA0 3. all readied dispatchable tasks are ineligible to be run on that processor
In case 1, all processors in the system are Idle. In case 2 and 3, there is at least one Active processor.
The execution of a task may cause another task to become available to the system. Therefore an Active processor may generate or ready a task such that there is a task in the system which can or must be performed by an Idle processor and which cannot be handled by the current set of Active processors. In order to maximize the utilization of all processors, there must be a means to allow an Idle processor to dispatch that task.
In prior art systems, where an Idle processor is typically placed in a wait state, this is accomplished by making an Active processor responsible for detecting the existence of an Idle processor and signalling the Idle processor that the work is available. The Idle processor then receives an interrupt, exits wait state and searches the queues of dispatchable tasks to find the readied task.
This processor checking and signalling by an Active processor and fielding the resulting interrupt by an Idle one delays the dispatching of the readied task and burdens the Active processor with work that represents undesired overhead. The delay is amplified on cache machines when techniques of status-checking and/or interrupt handling involve the examination of storage locations that were last modified by another processor. The degree of amplification depends upon the nature of the cache and the extent to which storage is modified in examination. For example, in a store-in cache machine such as the IBM 3081K the cache lines containing the "message" fields have to be discarded from the cache of the modifying processor and brought into the cache of the examining processor.
Prior art systems also face a timing problem in determining the status of potentially Idle processors. Prior to going into a wait state, a processor must scan the queues of potential work to determine that there are no available tasks and set a flag to indicate that it is in the wait state. After an Active processor readies a task that can be performed by an Idle processor, it checks the status flags of the potentially Idle processors. If the flag is checked after the "idle" processor has checked the work queues but prior to the setting of the Idle flag, the Active processor will be unable to detect that the Idle CPU is about to enter wait state. This problem has traditionally been solved by over-signalling although it could also be solved by serializing the entire scanning-flagging path. Both methods negatively impact system performance.
Accordingly, there is a need for a multiple processor system in which the dispatch of readied work is performed without excessive "overhead", that is, without utilizing excessive processor time that could otherwise be used for executing tasks.